package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/*
 * Find all pairs of two number whose sum is equal to a given number k 
 * complexity for distinct elements: O(nlogn) (sorting) + O(n) (scan)
 * */

public class SumOfTwo {

	// this works for distinct elements only
	// In case if duplicate values, number of duplicate pairs doesn't give correct results 
	public static List<String> findPairs(int[] arr, int k){
		// sort the array in case it's not sorted
		Arrays.sort(arr);
		
		List<String> pairs = new ArrayList<String>(); 
		
		for(int begin = 0, end = arr.length - 1; begin < end;){
			if(arr[begin] + arr[end] == k){
				if(!pairs.contains(arr[begin]+","+arr[end])) // add unique pairs only. this condition is not required as arr contains distinct values 
					pairs.add(arr[begin]+","+arr[end]); // first element will always be smaller as array is sorted
				begin++;
			}else if(arr[begin] + arr[end] > k){
				end--;
			}else {
				begin++;
			}
		}
		
		return pairs;
	}


	// for arr {1,2,3,3,4,5,6,7,7,7,7,9} and sum 10, all possible pairs: "1,9", "3,7", "3,7", "4,6"
	// for arr {4,5,6,7,7,7,7,9,1,2,3,3,6,4,10,10,0} and sum 10, all possible pairs: "0,10", "1,9", "3,7", "3,7", "4,6", "4,6"
	public static List<String> findPairsDuplicate(int[] arr, int k){
		
		// duplicate pairs
		List<String> pairsDuplicate = new ArrayList<String>();
		
		Set<Integer> elementsUnique = new HashSet<Integer>();
		
		// count occurrences of duplicate
		Map<Integer, Integer> occurenceMap = new HashMap<Integer, Integer>();
		for(int i: arr){
			elementsUnique.add(i); 
			if(occurenceMap.containsKey(i)){ // auto-boxing behind the scenes
				occurenceMap.put(i, (occurenceMap.get(i))+1);
			}else{
				occurenceMap.put(i, 1);
			}
		}
		
		// convert the set<Integer> to int[]
		int[] arrDistinct = new int[elementsUnique.size()];
		int index = 0;
		for(Integer i : elementsUnique){
			arrDistinct[index++] = i;
		}
		
		// find all unique pairs
		List<String> pairsUnique = findPairs(arrDistinct, k);
		
		// calculate duplicate pairs
		for(String pair : pairsUnique){
			int firstElement = Integer.parseInt(pair.substring(0, pair.indexOf(",")));
			int secondElement = Integer.parseInt(pair.substring(pair.indexOf(",")+1));
			int minOccrrence = occurenceMap.get(firstElement) > occurenceMap.get(secondElement) ? occurenceMap.get(secondElement) : occurenceMap.get(firstElement);
			
			while(minOccrrence >= 1){
				pairsDuplicate.add(pair);
				minOccrrence--;
			}
		}
		
		return pairsDuplicate;
	}

}
